class Node {
  constructor(element, parent) {
    this.element = element;
    this.parent = parent;
    this.left = null;
    this.right = null;
  }
}
// 实现二叉搜索树
// 先序： 根左右
// 中序： 左根右
// 后序： 左右根
class BinarySearchTree {
  constructor(compare) {
    this.root = null;
    this.size = 0;
    this.compare = compare || this.compare;
  }
  _root() {
    return this.root ? this.root : null;
  }
  compare(e1, e2) {
    return e1 - e2;
  }
  add(element) {
    if (this.root == null) {
      this.root = new Node(element, null);
      this.size++;
      return;
    } else {
      // 不是root节点，通过判断插入值的大小，区别插入左边还是右边
      let current = this.root;
      let compare = 0;
      let parent = null;
      while (current) {
        // compare = element - current.element;
        compare = this.compare(element, current.element);
        // 如果当前有元素，要继续向下层比较
        parent = current;
        if (compare > 0) {
          //  插入的值大，查找右树的元素作为当前节点【下次的root节点】，继续向下查找
          current = current.right;
        } else if (compare < 0) {
          // 否则查找左树
          current = current.left;
        } else {
          // 添加的元素已经存在
          current.element = element; //如果有重复的，用新的替换原来的
          return;
        }
      }
      // 左右都没有子元素给current赋值后，current为parent，为root，跳出while循环，
      let newNode = new Node(element, parent);
      if (compare > 0) {
        parent.right = newNode;
      } else {
        parent.left = newNode;
      }
    }
  }
  insert(element) {
    let newNode = new Node(element);
    this.root === null
      ? (this.root = newNode)
      : this.insertNode(this.root, newNode);
  }
  insertNode(node, newNode) {
    // newNode小于root元素放入左侧
    if (this.compare(newNode.element, node.element) < 0) {
      node.left === null
        ? (node.left = newNode)
        : this.insertNode(node.left, newNode);
    } else {
      node.right === null
        ? (node.right = newNode)
        : this.insertNode(node.right, newNode);
    }
  }
  min() {
    let node = this.root;
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.element;
    }
    return null;
  }
  max() {
    let node = this.root;
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.element;
    }
    return null;
  }
  /**
   * @description: 使用递归先序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  preOrderTraverse(visitor) {
    if (visitor === null) return;
    const traverse = (node) => {
      if (node === null) return;
      visitor.visit(node);
      traverse(node.left);
      traverse(node.right);
    };
    traverse(this.root);
  }
  /**
   * @description: 使用while循环先序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  preOrderTraverseWhile(visitor) {
    if (visitor === null) return;
    var stack = [this.root];
    while (stack.length !== 0) {
      var top = stack.pop();
      visitor.visit(top);
      if (top.right) {
        stack.push(top.right);
      }
      if (top.left) {
        stack.push(top.left);
      }
    }
  }
  /**
   * @description: 使用递归中序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  inOrderTraverse(visitor) {
    if (visitor === null) return;
    const traverse = (node) => {
      if (node === null) return;
      traverse(node.left);
      visitor.visit(node);
      traverse(node.right);
    };
    traverse(this.root);
  }
  /**
   * @description: 使用while循环中序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  inOrderTraverseWhile(visitor) {
    if (visitor === null) return;
    var stack = [];
    let result = [];
    let root = this.root;
    while (stack.length !== 0 || root) {
      while (root) {
        stack.push(root);
        root = root.left;
      }
      // stack.length有值
      root = stack.pop();
      result.push(root);
      root = root.right;
    }
    // console.log(result);
    result.forEach((res) => {
      visitor.visit(res);
    });
  }
  /**
   * @description: 使用递归后序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  postOrderTraverse(visitor) {
    if (visitor === null) return;
    const traverse = (node) => {
      if (node === null) return;
      traverse(node.left);
      traverse(node.right);
      visitor.visit(node);
    };
    traverse(this.root);
  }
  /**
   * @description: 使用while循环后序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  postOrderTraverseWhile(visitor) {
    if (visitor === null) return;
    var stack = [this.root];
    let result = [];
    while (stack.length !== 0) {
      var top = stack.pop();
      result.unshift(top);
      if (top.left) {
        stack.push(top.left);
      }
      if (top.right) {
        stack.push(top.right);
      }
    }
    result.forEach((res) => {
      visitor.visit(res);
    });
  }
  /**
   * @description: 使用递归层序遍历
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  levelorderTraverse(visitor) {
    let tree = [];
    tree.push(this.root);

    const traverse = (node) => {
      if (node == null) return;
      //   console.log(node);
      visitor.visit(node);
      if (node.left !== null) {
        tree.push(node.left);
      }
      if (node.right !== null) {
        tree.push(node.right);
      }
      traverse(tree.shift());
    };
    traverse(tree.shift());
  }
  /**
   * @description: 层序遍历，使用while循环
   * @param {*} visitor,访问者模式的方法
   * @return {*}
   */
  levelorderTraverseWhile(visitor) {
    if (visitor === null) return;
    let tree = [];
    tree.push(this.root);
    while (tree.length > 0) {
      let node = tree.shift();
      visitor.visit(node);
      if (node.left) {
        tree.push(node.left);
      }
      if (node.right) {
        tree.push(node.right);
      }
    }
  }
  /**
   * @description:
   * @param {*}
   * @return {*}
   */
  reverseBTree() {
    const reverse = (node) => {
      if (!node) return;
      let tmp = node.left;
      node.left = node.right;
      node.right = tmp;
      reverse(node.left);
      reverse(node.right);
    };
    reverse(this.root);
  }
  search(element) {
    return this._searchNode(this.root, element);
  }
  _searchNode(node, element) {
    if (node === null) {
      return false;
    }
    let compare = this.compare(element, node.element);
    if (compare < 0) {
      return this._searchNode(node.left, element);
    } else if (compare > 0) {
      return this._searchNode(node.right, element);
    } else {
      return true;
    }
  }
  remove(element) {
    let root = this._removeNode(this.root, element);
    return root;
  }
  _removeNode(node, element) {
    if (node === null) {
      return null;
    }
    let compare = this.compare(element, node.element);
    if (compare < 0) {
      node.left = this._removeNode(node.left, element);
      return node;
    } else if (compare > 0) {
      node.right = this._removeNode(node.right, element);
      return node;
    } else {
      // 一个页节点，没有子节点
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      // 只有一个子节点的节点
      if (node.left === null) {
        node = node.right; // 如果只有右节点，将右节点设置当前
        return node;
      } else if (node.right === null) {
        node = node.left; // 如果只有左节点，将左节点设置当前
        return node;
      }

      // 有两个子节点的节点
      let aux = this.findMinNode(node.right);
      node.element = aux.element;
      node.right = this._removeNode(node.right, aux.element);
      return node;
    }
  }
  findMinNode(node) {
    // 寻找前驱节点
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node;
    }
    return null;
  }
}
let bst = new BinarySearchTree((e1, e2) => {
  return e1.age - e2.age;
});
let arr = [10, 8, 19, 6, 15, 22, 20];
// 后边age为10的lisi会覆盖zs
let teams = [
  { age: 10, name: "zs" },
  { age: 8 },
  { age: 19 },
  { age: 6 },
  { age: 15 },
  { age: 22 },
  { age: 20 },
  { age: 10, name: "lisi" },
];
teams.forEach(function (element) {
  bst.add(element);
});
bst.insert({ age: 2 });
bst.remove({ age: 22 });
console.log(bst.min(), "min");
console.log(bst._root(), "_root");
console.log(bst.max(), "max");
console.log(bst.search({ age: 15 }));
// bst.reverseBTree();
// 使用访问者模式，对node进行处理
bst.preOrderTraverse({
  visit(node) {
    console.log(node.element, "---");
  },
});

// bst.levelorderTraverse();
